package pl.edu.agh.student.janikhankus.earley;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import pl.edu.agh.student.janikhankus.tree.Grammar;
import pl.edu.agh.student.janikhankus.tree.NonTerminal;
import pl.edu.agh.student.janikhankus.tree.Production;
import pl.edu.agh.student.janikhankus.tree.Symbol;

/**
 * CLass which is responsible for word parsing and creating Earley's situations set
 * @author tom
 *
 */
public class Earley {
	private ArrayList<OrderedDict> parseSets;
	private Map<Tuple, ArrayList<ParseProduction>> activeItems;
	/**
	 * Null productions list. Helps to resolve productions which may lead to epsilon.
	 */
	private Map<Symbol, TreeSet<ParseProduction>> nullable;
	//after parsing prints parse precedents (debug)
	private boolean printPrecedents = false;
	private boolean printMaxPrecedents = false;
	
	public Earley() {
	}

	//Adds precedents with a given production to parseSets. Check for possible epsilon productions.
	private void addItem(ParseProduction production, Precedents precedents) {
		int i = production.getI();
		int dot = production.getDot();
		int h = production.getH();
		Map<ParseProduction, TreeSet<Precedents>> currentParseSet = parseSets
				.get(i).d;
		if (currentParseSet.containsKey(production)) {
			if (!(precedents.getPredecessor() == null && precedents
					.getReduction() == null)) {
				currentParseSet.get(production).add(precedents);
			}
			return;
		}
		TreeSet<Precedents> tmpSetList = new TreeSet<Precedents>();
		if (precedents.getPredecessor() == null
				&& precedents.getReduction() == null) {
			currentParseSet.put(production, null);
		} else {
			tmpSetList.add(precedents);
			currentParseSet.put(production, tmpSetList);
		}

		parseSets.get(i).l.add(production);
		ArrayList<Symbol> tmpRightList = production.getRight();
		if (dot < tmpRightList.size()) {
			Symbol symbol = tmpRightList.get(dot);
			Tuple t = new Tuple(symbol, i);
			ArrayList<ParseProduction> tmpList;
			if (activeItems.containsKey(t)) {
				activeItems.get(t).add(production);
			} else {
				tmpList = new ArrayList<ParseProduction>();
				tmpList.add(production);
				activeItems.put(t, tmpList);
			}
			TreeSet<ParseProduction> tmpNullableList;
			if ((tmpNullableList = nullable.get(symbol)) == null) {
				return;
			}
			for (ParseProduction nullableProduction : tmpNullableList) {
				addItem(new ParseProduction(h, dot + 1, i,
						production.getLeft(), production.getRight(),
						production.getProbability()), new Precedents(
						production, nullableProduction));
			}
		}
	}

	/**
	 * Find every non terminal in grammar.
	 * @param grammar Specified grammar
	 * @return List of grammar's non terminals
	 */
	public ArrayList<Symbol> findNonTerminals(Grammar grammar) {
		ArrayList<Symbol> nTList = new ArrayList<Symbol>();
		for (Production p : grammar.getProductionList()) {
			for (Symbol s : p.getRight()) {
				if (s.asNonTerminal() != null) {
					nTList.add(s);
				}
			}
			if (p.getLeft().asNonTerminal() != null) {
				nTList.add(p.getLeft());
			}
		}
		return nTList;
	}

	/**
	 * Main method which parse word and return Earley's situations sets
	 * @param grammar Grammar with w
	 * @param tokens List of tokens (word components)
	 * @param nonterminals List of grammar non terminals
	 * @return List of Earley's situations set
	 */
	public ArrayList<OrderedDict> parse(Grammar grammar, List<String> tokens,
			ArrayList<Symbol> nonterminals) {
		parseSets = new ArrayList<OrderedDict>();
		parseSets.add(new OrderedDict());
		activeItems = new HashMap<Tuple, ArrayList<ParseProduction>>();
		nullable = new TreeMap<Symbol, TreeSet<ParseProduction>>();
		// Initial episol production add
		ArrayList<Symbol> startSymbol = new ArrayList<Symbol>();

		//Adding new start production: null -> S
		startSymbol.add((Symbol) grammar.getProductionList().get(0).getLeft());
		addItem(new ParseProduction(0, 0, 0, null, startSymbol, 0),
				new Precedents(null, null));
		for (int iter = 0; iter < tokens.size() + 1; iter++) {
			parseSets.add(new OrderedDict());
			ArrayList<ParseProduction> tmpIterList = new ArrayList<ParseProduction>();
			ArrayList<ParseProduction> iteredItemsList = new ArrayList<ParseProduction>();
			for (ParseProduction production : parseSets.get(iter).l) {
				tmpIterList.add(production);
				iteredItemsList.add(production);
			}

			while (true) {
				for (ParseProduction production : tmpIterList) {
					int dot = production.getDot();
					int h = production.getH();
					int rightSize = production.getRight().size();
					
					List<Symbol> right = production.getRight();
					if (dot == rightSize
							|| (right.size() == 1 && right.get(0).asEpsylon() != null)) {
						
						// Completer
						boolean epsProd = true;
						for (Symbol symbol : production.getRight()) {
							if (!nullable.containsKey(symbol)
									&& (symbol.asEpsylon() == null)) {
								epsProd = false;
								break;
							}
						}
						Symbol left = production.getLeft();
						if (epsProd) {

							if (nullable.containsKey(left)) {
								nullable.get(left).add(production);
							} else {
								TreeSet<ParseProduction> tmpList = new TreeSet<ParseProduction>();
								tmpList.add(production);
								nullable.put(left, tmpList);
							}
						}

						ArrayList<ParseProduction> tmpListA = activeItems
								.get(new Tuple(left, h));
						ArrayList<ParseProduction> tmpActivIterList = new ArrayList<ParseProduction>();
						ArrayList<ParseProduction> iteredActivItemsList = new ArrayList<ParseProduction>();
						if (tmpListA != null) {
							for (ParseProduction actiProduction : tmpListA) {
								tmpActivIterList.add(actiProduction);
								iteredActivItemsList.add(actiProduction);
							}
							while (true) {
								for (ParseProduction ci : tmpActivIterList) {

									addItem(new ParseProduction(ci.getH(),
											ci.getDot() + 1, iter,
											ci.getLeft(), ci.getRight(),
											ci.getProbability()),
											new Precedents(ci, production));

								}

								//If no extra element were added in loop - break
								//New productions could be added by addItem method
								if (iteredActivItemsList.size() == activeItems
										.get(new Tuple(left, h)).size()) {
									break;
								}
								// Adding new productions to iteration list
								tmpActivIterList = new ArrayList<ParseProduction>();
								for (int i = iteredActivItemsList.size(); i < activeItems
										.get(new Tuple(left, h)).size(); i++) {
									ParseProduction p = activeItems.get(
											new Tuple(left, h)).get(i);
									iteredActivItemsList.add(p);
									tmpActivIterList.add(p);
								}
							}
						}

					} else {
						Symbol symbol = (Symbol) production.getRight().get(dot);
						String symbolName = symbol.getName();
						
						//checking if right side of production is terminal - if true, go to scanner
						if (nonterminals.contains(symbol)) {
							ArrayList<Production> rightSides = new ArrayList<Production>();
							for (Production p : grammar.getProductionList()) {
								if (p.getLeft().getName().equals(symbolName)) {
									rightSides.add(p);
								}
							}
							// Predictor
							for (Production tmpRightSide : rightSides) {
								addItem(new ParseProduction(iter, 0, iter,
										(NonTerminal) symbol,
										tmpRightSide.getRight(),
										tmpRightSide.getProbability()),
										new Precedents(null, null));
							}
						} else {
							if (iter < tokens.size()
									&& symbol.getName()
											.equals(tokens.get(iter))) {
								// Scanner
								//Using final production - right side is terminal
								addItem(new ParseProduction(h, dot + 1,
										iter + 1, production.getLeft(),
										production.getRight(),
										production.getProbability()),
										new Precedents(production,
												new FinalProduction(0, 0, 0,
														null, tokens.get(iter))));
							}
						}
					}
				}
				//If no extra element were added in loop - break
				if (iteredItemsList.size() == parseSets.get(iter).l.size()) {
					break;
				}
				tmpIterList = new ArrayList<ParseProduction>();
				// Adding new productions to iteration list
				for (int i = iteredItemsList.size(); i < parseSets.get(iter).l
						.size(); i++) {
					iteredItemsList.add(parseSets.get(iter).l.get(i));
					tmpIterList.add(parseSets.get(iter).l.get(i));
				}

			}
		}

		//Debug
		ArrayList<Symbol> aa = new ArrayList<Symbol>();
		aa.add((Symbol) grammar.getProductionList().get(0).getLeft());

		if (printPrecedents) {
			if (printMaxPrecedents) {
				for (int iter = 0; iter < parseSets.size(); iter++) {
					Set<ParseProduction> jj = parseSets.get(iter).d.keySet();
					for (ParseProduction p : jj) {
						System.out.print("\n" + iter + " ");
						printParseProduction(p);
						TreeSet<Precedents> tmpPrecList = parseSets.get(iter).d
								.get(p);
						if (tmpPrecList != null) {
							for (Precedents prec : tmpPrecList) {
								printParseProduction(prec.getPredecessor());
								printParseProduction(prec.getReduction());

							}
						} else {
							System.out.println("prec list - null");
						}
					}
					System.out.println("");
				}
			} else {
				for (int iter = 0; iter < parseSets.size(); iter++) {
					Set<ParseProduction> jj = parseSets.get(iter).d.keySet();
					for (ParseProduction p : jj) {
						System.out.print(iter + " ");
						printParseProduction(p);
					}
					System.out.println();
				}
			}

		}

		return parseSets;
	}

	/**
	 * Print parse productions elements on console output
	 * @param p Parse production to print
	 */
	public static void printParseProduction(ParseProduction p) {
		String s = "";
		if (p == null) {
			System.out.println("null");
			return;
		}
		if (p instanceof FinalProduction) {
			System.out.println("final: " + ((FinalProduction) p).getTerminal());
			return;
		}
		if (p.getLeft() != null)
			s = s + p.getLeft().getName() + " -> ";
		else
			s = s + p.getLeft() + " -> ";
		String r = "";
		for (Symbol a : p.getRight()) {
			r = r + a.getName();
		}
		s = s + r + " | ";
		s = s + "dot: " + p.getDot();
		s = s + ", h: " + p.getH();
		s = s + ", i: " + p.getI();
		System.out.println(s);
	}

	/**
	 * Print productions elements on console output
	 * @param p Production to print
	 */
	public static void printProduction(Production p) {
		String s = "";
		String leftName;
		if (p.getLeft() == null) {
			leftName = null;
		} else {
			leftName = p.getLeft().getName();
		}
		s = s + leftName + " -> ";
		String r = "";
		for (Symbol a : p.getRight()) {
			r = r + a.getName();
		}
		s = s + r;
		System.out.println(s);
	}

}
